// https://leetcode.cn/problems/find-all-anagrams-in-a-string/

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size(), m = p.size();

        if (n < m)
            return vector<int>();

        vector<int> ans;
        vector<int> target(26);
        vector<int> mod(26);
        for (int i = 0; i < m; i++) {
            mod[p[i] - 'a']++;
            target[s[i] - 'a']++;
        }

        if (target == mod) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < n - m; i++) {
            target[s[i] - 'a']--;
            target[s[i + m] - 'a']++;

            if (target == mod) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};